Network coding (sometimes referred to simply as “coding”) is a new research area that may have interesting applications in practical networking systems. With network coding, intermediate nodes, instead of only forwarding the incoming packets, may send out packets that are linear combinations of previously received information. There are two main benefits of this approach: potential throughput improvements and a high degree of robustness.
Communication networks today share the same fundamental principle of operation. Whether it is packets over the Internet, or signals in a phone network, information is transported in the same way as cars share a highway. That is, independent data streams may share network resources, but the information itself is separate. Routing, data storage, error control, and generally all network functions are based on this assumption.
Network coding breaks this assumption. Instead of simply forwarding data, nodes may recombine several input packets into one or several output packets. Linear network coding uses a linear combination of the data, interpreted as numbers over some finite field. This allows for a much larger degree of flexibility in the way packets can be combined. Network coding is very well suited for environments where only partial or uncertain information is available for decision making. Successful reception of information does not depend on receiving specific packet content but rather on receiving a sufficient number of independent packets.
Linear combining requires enhanced computational capabilities at the nodes of the network. However, according to Moore's law, processing is becoming less and less expensive. The bottleneck has shifted to network bandwidth to support the ever-growing demand in applications and QoS guarantees over large unreliable networks. Network coding utilizes cheap computational power to increase network efficacy.
With the introduction of third-generation cellular systems over the last decade, there has been both a significant increase in the capacity of wireless networks and a growing use of wireless communication for data transmission. An essential feature of the newly emerging wireless networks is the transmission of files to multiple (potentially heterogeneous) receivers, as exemplified by transmission of video or music files. While the most common approach to data transmission builds on the scheduling/routing approach, where information is transmitted to one of multiple receivers as a function of their channel conditions, it has also been recognized that broadcasting to multiple receivers using network coding may be more efficient for utilizing the capacity of the network.
Although these throughput gains may appear to imply gains in delay through Little's law, this is not the case since coding is performed over large blocks and each packet in the block must await the completion of the whole block before it can be decoded. Despite considerable practical interest in the use of network coding in wireless communication systems, gains in delay performance resulting from network coding relative to traditional scheduling have not been analyzed or quantified. The best setting to investigate such gains is the rateless transmission scenario, where data of fixed length is to be communicated over the channel. In this context, the comparison in delay performance between traditional schemes and network coding is performed through the completion times of the whole data.